#include "marsexplorer_heuristic.h"

#include "../../globals.h" /** contains g_variable_domain, g_operators etc */
#include "../../operator.h"
#include "../../option_parser.h"
#include "../../plugin.h"
#include "../../state.h"

#include <stdio.h>
#include <limits>
#include <utility>
#include <math.h>
#include <iterator>
#include "regex.h"

using namespace std;


/** if TRUE, lots of debug will be cout'ed */
bool DEBUG = false;  
/** determines how expensive consuming/ignoring a food is
 *  (actually not very important for satisficing planning) */
float FOOD_PENALTY = 30.0f;  

/** \brief constructor */
MarsExplorerHeuristic::MarsExplorerHeuristic(const Options &opts)
    : Heuristic(opts) {
    min_operator_cost = numeric_limits<int>::max();
    for (int i = 0; i < g_operators.size(); ++i)
        min_operator_cost = min(min_operator_cost,
                                get_adjusted_cost(g_operators[i]));

    /** regular expressions to match specific fact names or operators */
    regex_t RE_food_at;  /** position of a food object */
    regcomp(&RE_food_at, ".*food-at\\(f([0-9]*), pos-([0-9]*)-([0-9]*).*\\).*", REG_EXTENDED|REG_ICASE);
    RE["RE_food_at"] = RE_food_at;
    
    regex_t RE_agent_at;  /** position of an agent */
    regcomp(&RE_agent_at, ".*agent-at\\(a([0-9]*), pos-([0-9]*)-([0-9]*).*\\).*", REG_EXTENDED|REG_ICASE);
    RE["RE_agent_at"] = RE_agent_at;
    
    regex_t RE_mothership_at;  /** position of a mothership; operator because the pos. variable gets compiled away */
    regcomp(&RE_mothership_at, ".*tidyup-at-mothership f([0-9]*) pos-([0-9]*)-([0-9]*)", REG_EXTENDED|REG_ICASE);
    RE["RE_mothership_at"] = RE_mothership_at;
    
    regex_t RE_food_with;  /** food carried by an agent */
    regcomp(&RE_food_with, ".*food-with\\(f([0-9]*), a([0-9]*)\\)", REG_EXTENDED|REG_ICASE);
    RE["RE_food_with"] = RE_food_with;
    
    regex_t RE_done;  /** switched to soft-goal fulfilling mode */
    regcomp(&RE_done, "^(|.*[^-])done.*", REG_EXTENDED|REG_ICASE);
    RE["RE_done"] = RE_done;
    
    regex_t RE_food_processed;  /** (soft-goal) */
    regcomp(&RE_food_processed, "^(|.*[^-])food-processed\\(f([0-9]*)\\)", REG_EXTENDED|REG_ICASE);
    RE["RE_food_processed"] = RE_food_processed;
    
    regex_t RE_food_consumed;  /** a food has been consumed by an agent */
    regcomp(&RE_food_consumed, ".*food-consumed\\(f([0-9]*)\\)", REG_EXTENDED|REG_ICASE);
    RE["RE_food_consumed"] = RE_food_consumed;
    
    regex_t RE_energy_decrement_is_active;  /** after each movement action, decrease an agent's energy */
    regcomp(&RE_energy_decrement_is_active, "^(|.*[^-])decrease-energy-by-([0-9]*).*", REG_EXTENDED|REG_ICASE);
    RE["RE_energy_decrement_is_active"] = RE_energy_decrement_is_active;
    
    regex_t RE_energy_increment_is_active;  /** after each movement action, decrease an agent's energy */
    regcomp(&RE_energy_increment_is_active, "^(|.*[^-])increase-energy.*", REG_EXTENDED|REG_ICASE);
    RE["RE_energy_increment_is_active"] = RE_energy_increment_is_active;
    
    regex_t RE_energy_level;  /** an agent's current energy level */
    regcomp(&RE_energy_level, "^(|.*[^-])energy-level-([0-9]*)\\(.*", REG_EXTENDED|REG_ICASE);
    RE["RE_energy_level"] = RE_energy_level;

    /** position used as starting point in the dijkstra routine
     *  this position is cached to speed up multiple successive requests */
    dijkstra_target.first = -1;
    dijkstra_target.second = -1;

    /** used to steer reading/initializing of the world map */
    initialized = false;
}

/** \brief destructor */
MarsExplorerHeuristic::~MarsExplorerHeuristic() {
    /** regular expressions */
    for (map<string,regex_t>::iterator it = RE.begin(); it != RE.end(); ++it)
        regfree(&((*it).second));
    RE.clear();
    
    /** world map */
    for (int i = 0; i < mymap.size(); i++)
    {
        mymap[i].clear();
        dist_from_mothership[i].clear();
    }
    mymap.clear();

    /** persistent dijkstra distances from mothership */
    dist_from_mothership.clear();

    /** drain dijkstra's priority queue */
    while (!dijkstra_pq.empty())
        dijkstra_pq.pop();
}

/** \brief (FastDownward internal) */
void MarsExplorerHeuristic::initialize() {
    cout << "Initializing (Domain specific) MarsExplorer heuristic..." << endl;
}

/** \brief main usage method: heuristic value of a state */
int MarsExplorerHeuristic::compute_heuristic(const State &state) {

    /** if the map is uninitialized, build it (should only happen once) */
    if (!initialized)
        read_map();

    /** copy the state for later access to (private) atoms etc. */
    const state_var_t *vars = state.get_buffer();
    
    vector< vector<int> > food_positions;       /** map positions of all food objects */
    vector<int> food_indices;                   /** PDDL food names are "f<index>" */
    vector< vector<int> > agent_positions;      /** map positions of agents */
    vector< vector<int> > mothership_position;  /** map positions of motherships */
    vector<int> processed_foods;                /** (soft goal) indices of processed food objects */
    vector<int> consumed_foods;                 /** indices of consumed food objects */
    
    bool agent_is_carrying_food = false;    
    bool done = false;
    int carried_food = -1;                      /** index of a carried food */
    int energy_level = -1;                      /** agent's current energy */
    int energy_change = 0;                      /** eat-food: +1, move-unladen: -1, move-laden: -2 */

    /** regular expressions */
    int nmatch = 4;                             /** counter for how many RE groups to expect */
    regmatch_t *pmatch = new regmatch_t[nmatch];/** saves RE groups */
    char *buf = new char[10];                   /** objects' indices (10 digits are plenty) */

    if (DEBUG) cout << endl;
    
    /** match variables against REs */
    for (size_t i = 0; i < g_variable_domain.size(); ++i)
    {
        /** the variable's valuation */
        string s = g_fact_names[i][static_cast<int>(vars[i])];
        const char *s_cstr = s.c_str();

        /** find out if the agent has switched to soft-goal mode */
        int reti = regexec(&RE["RE_done"], s_cstr, 0, NULL, 0);
        if(!reti)
        {
            if (DEBUG) cout << "RE_done fired on \"" << s_cstr << "\"" << endl;
            done = true;
            continue;
        }
        
        /** agent's current energy level */
        reti = regexec(&RE["RE_energy_level"], s_cstr, nmatch, pmatch, 0);
        if (!reti)
        {
            sprintf(buf, "%.*s", pmatch[2].rm_eo - pmatch[2].rm_so, &s_cstr[pmatch[2].rm_so]);
            energy_level = atoi(buf);
            if (DEBUG) cout << "RE_energy_level read " << energy_level << " on \"" << s_cstr << "\"" << endl;
            continue;
        }

        /** check if an energy-decreasing atom is active */
        reti = regexec(&RE["RE_energy_decrement_is_active"], s_cstr, nmatch, pmatch, 0);
        if (!reti)
        {
            if (DEBUG) cout << "RE_energy_decrement_is_active fired on \"" << s_cstr << "\"" << endl;
            sprintf(buf, "%.*s", pmatch[2].rm_eo - pmatch[2].rm_so, &s_cstr[pmatch[2].rm_so]);
            energy_change = -1 * atoi(buf);
            continue;
        }

        /** check if the energy-increasing atom is active */
        reti = regexec(&RE["RE_energy_increment_is_active"], s_cstr, 0, NULL, 0);
        if (!reti)
        {
            if (DEBUG) cout << "RE_energy_increment_is_active fired on \"" << s_cstr << "\"" << endl;
            energy_change = 1;
            continue;
        }
        
        /** foods that have already been processed */
        reti = regexec(&RE["RE_food_processed"], s_cstr, nmatch, pmatch, 0);
        if (!reti)
        {
            if (DEBUG) cout << "RE_food_processed fired on \"" << s_cstr << "\"" << endl;
            sprintf(buf, "%.*s", pmatch[2].rm_eo - pmatch[2].rm_so, &s_cstr[pmatch[2].rm_so]);
            processed_foods.push_back(atoi(buf));
            continue;
        }

        /** foods that have been consumed */
        reti = regexec(&RE["RE_food_consumed"], s_cstr, nmatch, pmatch, 0);
        if (!reti)
        {
            if (DEBUG) cout << "RE_food_consumed fired on \"" << s_cstr << "\"" << endl;
            sprintf(buf, "%.*s", pmatch[1].rm_eo - pmatch[1].rm_so, &s_cstr[pmatch[1].rm_so]);
            consumed_foods.push_back(atoi(buf));
            continue;
        }
        
        /** positions of food objects */
        reti = regexec(&RE["RE_food_at"], s_cstr, nmatch, pmatch, 0);
        if(!reti)
        {
            if (DEBUG) cout << "RE_food_at fired on \"" << s_cstr << "\"" << endl;
            sprintf(buf, "%.*s", pmatch[1].rm_eo - pmatch[1].rm_so, &s_cstr[pmatch[1].rm_so]);
            food_indices.push_back(atoi(buf));
            vector<int> pos;
            sprintf(buf, "%.*s", pmatch[2].rm_eo - pmatch[2].rm_so, &s_cstr[pmatch[2].rm_so]);
            pos.push_back(atoi(buf));
            sprintf(buf, "%.*s", pmatch[3].rm_eo - pmatch[3].rm_so, &s_cstr[pmatch[3].rm_so]);
            pos.push_back(atoi(buf));
            food_positions.push_back(pos);
            continue;
        }
        
        /** position of agent */
        reti = regexec(&RE["RE_agent_at"], s_cstr, nmatch, pmatch, 0);
        if(!reti)
        {
            if (DEBUG) cout << "RE_agent_at fired on \"" << s_cstr << "\"" << endl;
            vector<int> pos;
            sprintf(buf, "%.*s", pmatch[2].rm_eo - pmatch[2].rm_so, &s_cstr[pmatch[2].rm_so]);
            pos.push_back(atoi(buf));
            sprintf(buf, "%.*s", pmatch[3].rm_eo - pmatch[3].rm_so, &s_cstr[pmatch[3].rm_so]);
            pos.push_back(atoi(buf));
            agent_positions.push_back(pos);
            continue;
        }
        
        /** check if the agent is carrying a food object */
        reti = regexec(&RE["RE_food_with"], s_cstr, nmatch, pmatch, 0);
        if(!reti)
        {
            if (DEBUG) cout << "RE_food_with fired on \"" << s_cstr << "\"" << endl;
            agent_is_carrying_food = true;
            sprintf(buf, "%.*s", pmatch[1].rm_eo - pmatch[1].rm_so, &s_cstr[pmatch[1].rm_so]);
            carried_food = atoi(buf);
            continue;
        }
    }
    
    /** position of mothership 
      * FD seems to optimize the corresponding variable away, so we have to use operator names... */
    for (vector<Operator>::iterator iter = g_operators.begin(); iter != g_operators.end(); ++iter)
    {
        string s = (*iter).get_name();
        const char *s_cstr = s.c_str();

        int reti = regexec(&RE["RE_mothership_at"], s_cstr, nmatch, pmatch, 0);
        if(!reti)
        {
            if (DEBUG) cout << "RE_mothership_at fired on \"" << s_cstr << "\"" << endl;
            vector<int> pos;
            sprintf(buf, "%.*s", pmatch[2].rm_eo - pmatch[2].rm_so, &s_cstr[pmatch[2].rm_so]);
            pos.push_back(atoi(buf));
            sprintf(buf, "%.*s", pmatch[3].rm_eo - pmatch[3].rm_so, &s_cstr[pmatch[3].rm_so]);
            pos.push_back(atoi(buf));
            mothership_position.push_back(pos);
            break;
        }
    }

    /** tidy up */
    delete[] buf;
    delete[] pmatch;


    /** initialize the secondary distance map
     *  this map contains dijkstra distances from the mothership to all map cells */
    if (!initialized)
    {
        dijkstra_target.first  = mothership_position[0][0];
        dijkstra_target.second = mothership_position[0][1];

        dijkstra(&dist_from_mothership);

        /** only do this once; the mothership cannot move, the map cannot change */
        initialized = true;
    }
    

    /** compute the heuristic estimate as the sum of:
     *  - the sum of distances of all foods to the mothership
     *  - the distance of the agent to the nearest food that isn't being carried (if one exists) */
    float distance = 0;
    
    float xd, yd, tmp, tmp2;
    float nearest_food_dist = numeric_limits<float>::max();
    int nearest_food_manhattan_dist = -1;
    int agent_dijkstra_dist_to_mothership = dist_from_mothership[agent_positions[0][0]][agent_positions[0][1]];
    float dist_nearest_food_to_mothership = numeric_limits<float>::max();
    int nearest_food_to_mothership = -1;
    int nearest_food = -1;
    int nearest_food_index = -1;
    int i = 0;
    for (vector< vector<int> >::iterator iter = food_positions.begin(); iter != food_positions.end(); ++iter)
    {
        /** if a food has been consumed, it is not available anymore and does not count into the heuristic */
        bool consumed = false;
        for (int j = 0; j < consumed_foods.size(); ++j)
            if (food_indices[i] == consumed_foods[j])
                consumed = true;
        if (consumed)
            continue;
        
        tmp = (float)dist_from_mothership[(*iter)[0]][(*iter)[1]];
        distance += min(tmp, FOOD_PENALTY);

        xd = agent_positions[0][0] - (*iter)[0];
        yd = agent_positions[0][1] - (*iter)[1];
        tmp2 = sqrtf( xd*xd + yd*yd );

        /** the next nearest food to the mothership is helpful to determine whether the agent has enough energy for the next trip */
        if (tmp < dist_nearest_food_to_mothership && (mothership_position[0][0] != (*iter)[0] || mothership_position[0][1] != (*iter)[1]))
        {
            dist_nearest_food_to_mothership = tmp;
            nearest_food_to_mothership = food_indices[i];
        }
        
        /** the nearest food must not be one already delivered to the mothership (those cannot be picked up again) */
        if (tmp2 < nearest_food_dist && (mothership_position[0][0] != (*iter)[0] || mothership_position[0][1] != (*iter)[1]))
        {
            nearest_food_dist = tmp2;
            nearest_food_manhattan_dist = abs(agent_positions[0][0] - (*iter)[0]) + abs(agent_positions[0][1] - (*iter)[1]);
            
            nearest_food = food_indices[i];
            nearest_food_index = i;
        }
        ++i;
    }


    if (DEBUG && nearest_food_dist != numeric_limits<float>::max())
        cout << "Nearest food to agent is f" << nearest_food << " (with " << nearest_food_dist << ")" << endl;
    if (DEBUG && dist_nearest_food_to_mothership != numeric_limits<float>::max())
        cout << "Nearest food to mothership is f" << nearest_food_to_mothership << " (with " << dist_nearest_food_to_mothership << ")" << endl;
    
    if (agent_is_carrying_food) 
    {
        /** a carried food has no position variable and has to be treated separately */
        distance += agent_dijkstra_dist_to_mothership;
    }
    else if (nearest_food_dist != numeric_limits<float>::max())
    {
        /** if no food is being carried, the agent wants to get to one
         *  if the distance to the mothership via this nearest food is > FOOD_PENALTY, enforce admissibility */
        distance += min(nearest_food_dist, FOOD_PENALTY);        
    }


    /** if the remaining energy is insufficient to reach the target food, the state is a dead end
     *  (the similar case where the agent is carrying and trying to get back to the mothership
     *  can be resolved by eating the food, and is thus a preferred-operators-case) */
    if (!done && !agent_is_carrying_food && energy_level < nearest_food_manhattan_dist)
    {
        if (DEBUG) cout << "Energy insufficient to reach next food, returning." << endl;
        return numeric_limits<int>::max();
    }


    /** holds an operator's name (for marking as preferred) */
    char *opstr = new char[1024];


    /** set preferred operators
     *  these are ESSENTIAL to the success, as the search space is just too large, even for small worlds */
    if (!done && energy_change < 0)
    {
        /** if some energy decrement is necessary, choose the corresponding operator */
        sprintf(opstr, "decrease-energy-by-%d-from-%d", -1*energy_change, energy_level);
        mark_operator(opstr);
    }
    else if (!done && energy_change > 0)
    {
        /** (same for energy increment) */
        sprintf(opstr, "increase-energy");
        mark_operator(opstr);
    }
    else if (!done && !agent_is_carrying_food && nearest_food_dist == 0)
    {
        /** if the agent has arrived at a food item, pick it up */
        sprintf(opstr, "pick-up-food a0 f%d pos-%d-%d", nearest_food, agent_positions[0][0], agent_positions[0][1]);
        mark_operator(opstr);
    }
    else if (!done && agent_is_carrying_food && energy_level < 2)
    {
        /** if the agent is carrying food, but does not have enough energy
          * to do anything anymore, it should consume the food */
        sprintf(opstr, "eat-food a0 f%d", carried_food);
        mark_operator(opstr);
    }
    else if (!done && agent_is_carrying_food && agent_dijkstra_dist_to_mothership == 0)
    {
        /** if the agent has carried a food back to the mothership, then drop it there */
        sprintf(opstr, "drop-food a0 f%d pos-%d-%d", carried_food, mothership_position[0][0], mothership_position[0][1]);
        mark_operator(opstr);
    }
    else if (!done && agent_is_carrying_food && 
             dist_nearest_food_to_mothership < numeric_limits<float>::max() &&
             energy_level < (2*agent_dijkstra_dist_to_mothership + dist_nearest_food_to_mothership))
    {
        /** if the agent is carrying food, but does not have enough energy
         *  to bring the food back and make the next trip, it should
         *  go to the next food immediately */
        if (agent_positions[0][0] == food_positions[nearest_food_index][0] && agent_positions[0][1] == food_positions[nearest_food_index][1])
        {
            sprintf(opstr, "eat-food a0 f%d", carried_food);
            mark_operator(opstr);
        }
        else {
            dijkstra_move(agent_positions[0][0],
                          agent_positions[0][1],
                          food_positions[nearest_food_index][0],
                          food_positions[nearest_food_index][1],
                          true);
        }
    }
    else if (!done && agent_is_carrying_food)
    {
        /** if the agent is carrying a food object and has ample reserves, the preferred target is the mothership */
        dijkstra_move(agent_positions[0][0],
                 agent_positions[0][1],
                 mothership_position[0][0],
                 mothership_position[0][1],
                 true);
    }
    else if (!done && !agent_is_carrying_food && nearest_food_dist != numeric_limits<float>::max())
    {
        /** if the agent is not carrying anything, the preferred target is the nearest food object (if one exists) */
        dijkstra_move(agent_positions[0][0],
                      agent_positions[0][1],
                      food_positions[nearest_food_index][0],
                      food_positions[nearest_food_index][1],
                      false);
    }
    else if (done && food_indices.size() > 0) 
    {
        /** in soft-goal mode and there are unprocessed foods */
        
        /** if the foods are not processed in order, punish with "infinite" heuristic estimate
         *  effect: n foods span a realistic search space of O(n), as opposed to O(n!) */
        for (int i = 0; i < processed_foods.size(); i++)
            if (processed_foods[i] >= processed_foods.size())
                return numeric_limits<int>::max();

        /** find out if the next unprocessed food is consumed/in field (bad, expensive) or at the mothership (good, cheap) */
        int next_food = processed_foods.size();
        vector<int>::iterator iter = find(food_indices.begin(), food_indices.end(), next_food);
        int next_food_index = std::distance(food_indices.begin(), iter);
		if (next_food_index == food_indices.size())
		{
			/** an unprocessed food without position must have been consumed */
			sprintf(opstr, ".*tidyup-consumed f%d.*", next_food);
		}
        else if (food_positions[next_food_index][0] == mothership_position[0][0] && food_positions[next_food_index][1] == mothership_position[0][1])
        {
            /** food is at mothership */
            sprintf(opstr, ".*tidyup-at-mothership f%d pos-%d-%d.*", next_food, mothership_position[0][0], mothership_position[0][1]);
        }
        else
        {
            /** food is laying around in field */
            sprintf(opstr, ".*tidyup-in-field f%d pos-%d-%d.*", next_food, food_positions[next_food_index][0], food_positions[next_food_index][1]);
        }

        /** add operator to the preferred operators */
        mark_operator(opstr);
    }
    
    /** tidy up */
    delete[] opstr;

    /** return the heuristic value */
    if (test_goal(state))
        return 0;
    else
        return static_cast<int>(distance + 0.5);
}

/** for a given pair of coordinates, find a matching movement operator
 *  if such an operator is found, add it to the preferred_operators
 *  @param  agent_index         PDDL index of the agent
 *  @param  laden               TRUE iff the agent is carrying food
 *  @param  agent_x, agent_y    the agent's current position
 *  @param  target_x, target_y  where the agent wants to go
 **/
void MarsExplorerHeuristic::mark_move_operator(int agent_index, bool laden, int agent_x, int agent_y, int target_x, int target_y) {
    char *opstr = new char[1024];
	const char *lstr = (laden ? "move-laden" : "move-unladen");
    sprintf(opstr, ".*%s a%d pos-%d-%d pos-%d-%d.*", lstr, agent_index, agent_x, agent_y, target_x, target_y);
    mark_operator(opstr);

    delete[] opstr;
}

/** \brief adds an operator to "preferred_operators" whose name matches "opstr" (interpreted as regular expression)
 *  @param  opstr   Regular expression describing the name of the operator to be marked
 **/
void MarsExplorerHeuristic::mark_operator(char *opstr) {
    if (DEBUG) cout << "I want to mark " << opstr << endl;
    regex_t RE_op;
    regcomp(&RE_op, opstr, REG_EXTENDED|REG_ICASE);
    int i = 0;
    for (vector<Operator>::iterator iter = g_operators.begin(); iter != g_operators.end(); ++iter)
    {
        string s = (*iter).get_name();
        int reti = regexec(&RE_op, s.c_str(), 0, NULL, 0);
        if(!reti)
        {
            /** matching operator found */
            const Operator *op = &g_operators[i];
            /** (FD internal) */
            set_preferred(op);
            if (DEBUG) cout << "Operator " << op->get_name() << " marked" << endl;
            break;
        }
        ++i;
    }
    
    regfree(&RE_op);
}

/** \brief reads operator names, extracting information about positions that can
 *  be reached by move operations. this implies information about the map */
void MarsExplorerHeuristic::read_map() {
    regex_t RE_move;
    regcomp(&RE_move, ".*laden a0 pos-([0-9]*)-([0-9]*) pos-([0-9]*)-([0-9]*).*", REG_EXTENDED|REG_ICASE);
    int nmatch = 5;                              /** counter for how many RE groups to expect */
    regmatch_t *pmatch = new regmatch_t[nmatch]; /** saves RE groups */
    char *buf = new char[10];                    /** objects' indices (10 digits are plenty) */
    vector< pair<int, int> > walkable;           /** unobstructed map cells */
    
    /** NOTE: This is not completely accurate. The routine adds one row and one
     *  column of walls to the bottom/far right. The reason is that these are
     *  (usually) in the original map, but aren't reflected by the move-operators */
    int max_x = 0;
    int max_y = 0;

    for (vector<Operator>::iterator iter = g_operators.begin(); iter != g_operators.end(); ++iter)
    {
        string s = (*iter).get_name();
        int reti = regexec(&RE_move, s.c_str(), nmatch, pmatch, 0);
        if(!reti)
        {
            pair<int, int> pos;
            sprintf(buf, "%.*s", pmatch[1].rm_eo - pmatch[1].rm_so, &s.c_str()[pmatch[1].rm_so]);
            pos.first = atoi(buf);
            max_x = max(max_x, pos.first+2);
            sprintf(buf, "%.*s", pmatch[2].rm_eo - pmatch[2].rm_so, &s.c_str()[pmatch[2].rm_so]);
            pos.second = atoi(buf);
            max_y = max(max_y, pos.second+2);
            walkable.push_back(pos);
        }
    }

    /** blow maps up to size */
    for (int i = 0; i < max_x; i++)
    {
        vector<int> column;
        /** -2 is a marker for "here is a wall" */
        column.resize(max_y, -2);
        mymap.push_back(column);

        vector<int> column2;
        column2.resize(max_y, -2);
        dist_from_mothership.push_back(column2);
    }

    /** mark all walkable cells */
    for (vector< pair<int, int> >::iterator iter = walkable.begin(); iter != walkable.end(); ++iter)
    {
        /** -1 is the Dijkstra marker for "uninitialized cell" */
        try {
            mymap[(*iter).first][(*iter).second] = numeric_limits<int>::max();
            dist_from_mothership[(*iter).first][(*iter).second] = numeric_limits<int>::max();
        } catch(...) {
            cerr << "ERROR: writing map cell (" << (*iter).first << ", " << (*iter).second << ")" << endl;
        }
    }

    if (DEBUG) prettyprint_map();

    /** tidy up */
    walkable.clear();
    delete[] buf;
    delete[] pmatch;
    regfree(&RE_move);
}

/** \brief produces a nice layout of the map's wall structure
 *  (large maps lead to not-at-all-pretty linewraps...) */
void MarsExplorerHeuristic::prettyprint_map() {
    cout << endl;
    
    cout << "      ";
    for (int x = 0; x < mymap.size(); x++)
        printf("%5d",x);
    cout << endl;
    cout << "     +";
    for (int x = 0; x < mymap.size(); x++)
        printf("-----");
    cout << endl;
    
    for (int y = 0; y < mymap[0].size(); y++)
    {
        printf("%3d  |",y);
        for (int x = 0; x < mymap[y].size(); x++)
        {
            if (mymap[x][y] == numeric_limits<int>::max())
                printf("    -");
            else
                printf("%5d",mymap[x][y]);
        }
        cout << endl;
    }

    cout << endl;
    // (yes, just as hacky it looks. sorry.)
}


/** \brief marks a move operator based on dijkstra distances
 *  @param  startx, starty      current position
 *  @param  targetx, targety    target position
 *  @param  laden               TRUE iff agent is carrying food
 **/
void MarsExplorerHeuristic::dijkstra_move(int startx, int starty, int targetx, int targety, bool laden) {
    /** starting at a wall? that does not bode well */
    if (mymap[startx][starty] == -2)
    {
        cerr << "ERROR: dijkstra requested at wall position (" << startx << ", " << starty << ")!" << endl;
        return;
    }
    
    /** the cached target is deprecated; a new dijkstra run is necessary */
    if (targetx != dijkstra_target.first || targety != dijkstra_target.second)
    {
        dijkstra_target.first = targetx;
        dijkstra_target.second = targety;

        dijkstra(&mymap);
    }

    /** read out the neighboring cells' values */
    int a = mymap[startx][starty];
    int *vals = new int[4];
    
    if (startx > 0)  /** western neighbor */
    {
        int el = mymap[startx-1][starty];
        if (el >= 0 && el < a)
            vals[0] = el;
        else
            vals[0] = numeric_limits<int>::max();
    }
    if (startx < mymap.size()-1)  /** eastern neighbor */
    {
        int el = mymap[startx+1][starty];
        if (el >= 0 && el < a) 
            vals[1] = el;
        else
            vals[1] = numeric_limits<int>::max();
    }
    if (starty > 0)  /** northern neighbor */
    {
        int el = mymap[startx][starty-1];
        if (el >= 0 && el < a) 
            vals[2] = el;
        else
            vals[2] = numeric_limits<int>::max();
    }
    if (starty < mymap[0].size()-1)  /** southern neighbor */
    {
        int el = mymap[startx][starty+1];
        if (el >= 0 && el < a) 
            vals[3] = el;
        else
            vals[3] = numeric_limits<int>::max();
    }

    /** find the minimum */
    int min = numeric_limits<int>::max();
    for (int i = 0; i < 4; i++)
        if (vals[i] < min)
            min = vals[i];

    /** mark the corresponding movement operator(s) */
    if (min != numeric_limits<int>::max())
    {    
        if (vals[0] == min)
            mark_move_operator(0, laden, startx, starty, startx-1, starty);
        if (vals[1] == min)
            mark_move_operator(0, laden, startx, starty, startx+1, starty);
        if (vals[2] == min)
            mark_move_operator(0, laden, startx, starty, startx, starty-1);
        if (vals[3] == min)
            mark_move_operator(0, laden, startx, starty, startx, starty+1);
    }

    /** tidy up */
    delete[] vals;
}
    

/** \brief computes Dijkstra distances from point dijkstra_target (on the whole walkable map)
 *  @param  themap      the map in which to store the computed distances
 **/
void MarsExplorerHeuristic::dijkstra(vector< vector<int> > *themap) {

    /** reset priority queue */
    while (!dijkstra_pq.empty())
        dijkstra_pq.pop();

    /** reset (=reinitialize) map... */
    for (int x = 0; x < themap->size(); x++)
        for (int y = 0; y < (*themap)[x].size(); y++)
            if ((*themap)[x][y] != -2)
            {
                (*themap)[x][y] = numeric_limits<int>::max();
                pair< int, pair<int, int> > p;
                p.first = (*themap)[x][y];
                p.second.first = x;
                p.second.second = y;
                dijkstra_pq.push(p);
            }
    (*themap)[dijkstra_target.first][dijkstra_target.second] = 0;
    /** ...and priority queue */
    pair< int, pair<int, int> > p;
    p.first = 0;
    p.second.first = dijkstra_target.first;
    p.second.second = dijkstra_target.second;
    dijkstra_pq.push(p);

    /** Dijkstra's algorithm */
    while (!dijkstra_pq.empty())
    {
        pair< int, pair<int, int> > node = dijkstra_pq.top();
        dijkstra_pq.pop();
        
        int x = node.second.first;
        int y = node.second.second;
        int dist = node.first;

        if (dist == numeric_limits<int>::max())
            break;

        /** the STL priority queue does not support a decrease_key() operation,
         *  so we have to handle multiple occurances of the same node */
        if (dist > (*themap)[x][y])
            continue;

        /** push next cells onto PQ (unless they contain walls) */
        if (x > 0 && (*themap)[x-1][y] != -2)
            dijkstra_pushnewneighbor(x-1, y, dist, themap);
        if (x < themap->size()-1 && (*themap)[x+1][y] != -2)
            dijkstra_pushnewneighbor(x+1, y, dist, themap);
        if (y > 0 && (*themap)[x][y-1] != -2)
            dijkstra_pushnewneighbor(x, y-1, dist, themap);
        if (y < (*themap)[0].size()-1 && (*themap)[x][y+1] != -2)
            dijkstra_pushnewneighbor(x, y+1, dist, themap);
        
    }
}

/** \brief expands a (neighboring) node in dijkstra and pushes it onto the priority queue
 *  @param  x, y        the cell to be pushed
 *  @param  dist        the parent cell's dijkstra distance
 *  @param  themap      the map in which to store the results
 **/
void MarsExplorerHeuristic::dijkstra_pushnewneighbor(int x, int y, int dist, vector< vector<int> > *themap) {
    int nd = dist + 1;
    if (nd < (*themap)[x][y])
    {
        (*themap)[x][y] = nd;
        pair< int, pair<int, int> > n;
        n.first = nd;
        n.second.first = x;
        n.second.second = y;
        dijkstra_pq.push(n);
    }
}

/** \brief (FD internal) */
static ScalarEvaluator *_parse(OptionParser &parser) {
    Heuristic::add_options_to_parser(parser);
    Options opts = parser.parse();
    if (parser.dry_run())
        return 0;
    else
        return new MarsExplorerHeuristic(opts);
}

static Plugin<ScalarEvaluator> _plugin("marsexplorer", _parse);
